// 分割回文串
class Solution {
    vector<vector<string>> res;
    vector<string> path;
public:
    vector<vector<string>> partition(string s) {
        dfs(s, 0);
        return res;
    }
    void dfs(string& s, int pos)
    {
        if (pos == s.size())
        {
            res.push_back(path);
            return;
        }
        for (int i = pos; i < s.size(); i++)
        {
            if (check(s, pos, i))
            {
                path.push_back(s.substr(pos, i - pos + 1));
                dfs(s, i + 1);
                path.pop_back();
            }
        }
    }
    bool check(string& s, int l, int r)
    {
        while (l < r && s[l] == s[r])
        {
            l++, r--;
        }
        return l >= r;
    } 
};
